package com.cat.dataStructure03;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/append-k-integers-with-minimal-sum/
 * @create 2025/11/10 15:53
 * @since JDK17
 */

public class Solution37 {
    public long minimalKSum(int[] a, int k) {
        int[] nums = new int[a.length + 1];
        nums[0] = 0;
        for (int i = 0; i < a.length; i++) {
            nums[i + 1] = a[i];
        }
        int n = nums.length;
        long ans = 0;
        Arrays.sort(nums);
        for (int i = 1; i < n && k > 0; i++) {
            int d = nums[i] - nums[i - 1] - 1;  // 中间的缝隙
            if (d <= 0) {
                continue;
            }
            if (d < k) {
                ans += (long) (nums[i - 1] + nums[i]) * d / 2;
                k -= d;
            } else {    // 不够了
                ans += (long) (nums[i - 1] + 1 + nums[i - 1] + k) * k / 2;
                k = 0;
            }
        }
        if (k > 0) {
            ans += (long) (nums[n - 1] + 1 + nums[n - 1] + k) * k / 2;
        }

        return ans;
    }
}
